package combination

var mapping = map[byte][]byte{
	'2': {'a', 'b', 'c'},
	'3': {'d', 'e', 'f'},
	'4': {'g', 'h', 'i'},
	'5': {'j', 'k', 'l'},
	'6': {'m', 'n', 'o'},
	'7': {'p', 'q', 'r', 's'},
	'8': {'t', 'u', 'v'},
	'9': {'w', 'x', 'y', 'z'},
}

func letterCombinations(digits string) []string {
	if len(digits) == 0 { //注意空的时候不能返回[""]
		return []string{}
	}
	return combination("", digits, []string{})
}

//1. 递归结束的条件
//2. 递归结束的时候，写入符合条件的数据到结果集
//3. 参数传入中间结果 如tmp字符串。
func combination(tmp, digits string, result []string) []string {
	//递归结束条件
	if len(tmp) == len(digits) {
		result = append(result, tmp)
		return result
	}
	bytes := mapping[digits[len(tmp)]]
	for _, b := range bytes {
		//回溯法
		result = combination(tmp+string(b), digits, result)
	}
	return result
}
